import java.util.Stack;

/**
 * Created by L.jp
 * Description:给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 * User: 86189
 * Date: 2022-07-03
 * Time: 10:02
 */
//遇到左括号就入栈，遇到右括号要看当前的字符是否和栈顶的字符匹配，不匹配直接返回false
    //遍历结束，最后判断stack是否为空，不为空说明不匹配，返回false
public class Solution {
    public boolean isValid (String s) {
        int len=s.length();
        if(len==0){
            return false;
        }
        if(len%2!=0){
            return false;
        }
        Stack<Character> stack=new Stack<>();
        for(int i = 0; i < len; i++){
            char c = s.charAt(i);
            //遇到左括号就入栈
            if(c=='{' || c=='[' || c=='('){
                stack.push( c);
            }else{
                //遇到右括号要看看栈顶元素跟当前元素是不是匹配，不匹配就返回false
                if(stack.isEmpty()){
                    //要么遇到了左括号，要么右括号，如果第一个遇到的就是右括号那直接返回false
                    return false;
                }
                char ch=stack.peek();
                if(ch=='{' && c=='}' || ch=='[' && c==']' || ch=='(' && c==')'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
